package _11_整理题目._2_二叉树_递归_dfs_bfs._dfs_路径和;


import org.junit.Test;
import util.TreeNode;

import java.util.ArrayList;

/**
 * https://leetcode-cn.com/problems/path-sum-ii/
 *
 * 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
 * 
 */
public class _062_找出所有二叉树根节点到叶子节点和为指定值的路径 {
    
    private ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    private ArrayList<Integer> path = new ArrayList<>();
    
    public ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int target) {
        dfs(root, 0, target);
        return result;
    }

    private void dfs(TreeNode root, int sum, int target) {
        if (root == null) return;

        sum += root.val;
        path.add(root.val);
        if (root.left == null && root.right == null && sum == target) {
            result.add(new ArrayList<>(path));
        }

        dfs(root.left, sum, target);
        dfs(root.right, sum, target);

        path.remove(path.size()-1);
    }

    @Test
    public void main() {
        Integer[] input = {5, 4, 8, 1, 11, null, 9, null, null, 2, 7};
        TreeNode root = TreeNode.getTreeFromArray(input);
        ArrayList<ArrayList<Integer>> result = pathSum(root, 22);
        result.forEach(list -> System.out.println(list));
    }
}
